package com.jn.algorithm.day011.question34;

import java.util.Arrays;

/**
 * @author 江南大学1033190417
 * @date 2022/4/26 21:01
 */
public class Solution {

    //二分查找
    public int[] searchRange(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) {
            return new int[]{-1, -1};
        }
        if (length == 1) {
            if (nums[0] == target) {
                return new int[]{0, 0};
            }
            return new int[]{-1, -1};
        }
        int left = 0, right = length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                int t1 = mid, t2 = mid;
                while (t1 - 1 >= 0) {
                    if (nums[t1 - 1] == target) {
                        --t1;
                    } else
                        break;
                }
                while (t2 + 1 < length) {
                    if (nums[t2 + 1] == target) {
                        ++t2;
                    } else
                        break;
                }
                return new int[]{t1, t2};
            } else if (nums[mid] > target) {//如果那个数在左边
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int[]{-1, -1};
    }

    //线性搜索
    public int[] searchRange2(int[] nums, int target) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] == target) {
                int temp = i;
                while (temp + 1 <= length - 1) {
                    if (nums[temp + 1] == target) {
                        ++temp;
                    } else {
                        break;
                    }
                }
                return new int[]{i, temp};
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{1, 2, 3, 3, 3, 3, 4, 5, 9};
        int target = 3;
        System.out.println(Arrays.toString(solution.searchRange(nums, target)));
    }
}
